\section{Введение}

Часто возникают задачи, для которых неизвестно быстрого (т.е. полиномиального) алгоритма, дающего оптимальное решение. 
Такие задачи относятся к классу NP, и нахождение оптимального решения для них представляется невозможным из-за высокой вычислительной сложности. 
Тем не менее, такого рода задачи приходится решать, поэтому встает вопрос о быстром нахождении решения, 
как можно более близкого к оптимальному. Этой задачей занимается особый вид алгоритмов, называемых \flqqстохастическими\frqq. 
Одним из таких алгоритмов является \flqqАлгоритм имитации отжига\frqq\ (\mbox{англ.}~Simulated Annealing), которому и посвящена моя работа.

В своей работе я кратко изложил принцип работы этого алгоритма, а также применил его на практике к такой NP-полной задаче, как 
задача коммивояжера. Также рассмотрены способы параллелизации этого алгоритма, и в качестве практического приложения выполнена 
реализация \flqqпараллельного\frqq\ варианта алгоритма на GPU с помощью технологии NVIDIA CUDA.